package leetcode_800;

import helpclass.ListNode;

/**
 *@author 周杨
 *SplitLinkedListInParts_725 将一个链表分成K份  空出来的用null实现
 *describe:常规方法 AC 11%
 *2018年10月12日 下午8:52:19
 */
public class SplitLinkedListInParts_725 {
	
	public static void main(String[] args) {
		
	}
	
	public ListNode[] splitListToParts(ListNode root, int k) {
        ListNode[] res = new ListNode[k];
        if(root == null){
            return res;
        }
        
        int listSize = size( root);
        //all list will be size 1 and left over k, remains empty
        if(listSize <= k){
            int i = 0;
            ListNode curr = root;
            while(curr != null){
                
                ListNode currNext = curr.next;
                res[i] = curr;
                curr.next = null;
                curr = currNext;
                i++;
            }
        }
        else{
            //every list must have these many
            int everyListnumElem = listSize/k;
            //these are elements that are still remaining, we will add them one by one 
            int leftOver = listSize - everyListnumElem*k;
             ListNode curr = root;

            //starting from list 0
            int j = 0;
            
            while(j < k  ){
                //number of element added to the curr list
                int elementAdded = 0;
                //make a dummynode
                ListNode dummy = new ListNode(-44);
                //this will fill the curr list we are building
                ListNode dummyRunner = dummy;

                //number of elements added are not more than limit, add one
                while(curr != null && elementAdded < everyListnumElem){
                    dummyRunner.next = curr;
                    curr = curr.next;
                    dummyRunner = dummyRunner.next;
                    elementAdded++;
                }
                //add one extra to the list and decrease leftover count
                if(leftOver > 0 ){
                    dummyRunner.next = curr;
                   dummyRunner =  dummyRunner.next;
                    curr = curr.next;

                    leftOver--;
                } 

                //dont forget split this list that you are adding 
                dummyRunner.next = null;
                //add the list to result
                res[j]  =dummy.next;

    
                j++;
   
             }
            
        }
        
        return res;
    }
    
    public int size(ListNode root){
        int i = 0;
        while(root != null){
            i++;
            root =root.next;
        }
        return i;
    }
}
